强烈推荐，超详细实现二叉树的建立（附实现源码） |
您所在的位置：网站首页 › 中序遍历 先序遍历 › 强烈推荐，超详细实现二叉树的建立（附实现源码） |
强烈推荐，超详细实现二叉树的建立（附实现源码）
|
目录
1.如何创建一棵二叉树1.二叉树的存储结构定义2.实现二叉树结点的新建、查找、修改3.实现二叉树结点的插入4.二叉树创建过程
2.二叉树的遍历1.先序遍历2.中序遍历3.后序遍历4.层序遍历
3.源码实现
1.如何创建一棵二叉树
创建一棵二叉树需要什么 其实答案很简单，无非就是从根节点开始，逐步实现子节点的创建，从而实现树的整体框架 由于树是一种特殊的线性表，所以对于生成后的树，我们应该可以对它进行查找，修改，插入等功能 最后，我们将进行对树的遍历，这里将讨论常用的先序，中序，后序以及层序等四种遍历方式 关于二叉查找树结点的删除，可以查看后续文章 强烈推荐！超详细实现二叉查找树结点的删除（附实现源码） 1.二叉树的存储结构定义 一般来说，二叉树使用链表来定义，不同的是，由于二叉树每个结点都存在两条出边，因此指针域变为两个，分别指向左子树和右子树的跟结点地址，因此又把这种链表叫做二叉链表 struct node { int data; //数据域 node * lchild; //指向左子树根节点的指针 node * rchild; //指向右子树根节点的指针 }; 2.实现二叉树结点的新建、查找、修改 如果需要新建结点（例如往二叉树里面插入结点时，可使用下面的函数（返回类型是一个指向node的指针） node* newNode(int v) { node*Node = new node; //申请一个node类型变量的地址空间 Node->data = v; //结点权值为v Node->lchild = Node->rchild = NULL; //初始状态下无左右孩子 return Node; //返回新节点的地址 } 查找操作是指在给定的数据域内，在二叉树里面找到所有数据域（对多个结点实行操作）为给定数据域的结点，并且对查找到的结点修改为给定的数据域 void search(node*root,int x, int newdata){ if (root == NULL) return; //考虑为空节点的可能性 if (root->data == x) { root->data = newdata; //找到数据域为x的结点，把它修改为newdata } search(root->lchild, x, newdata);//往左子树搜索 search(root->rchild, x, newdata);//往右子树搜索 } 3.实现二叉树结点的插入 关于二叉树结点的插入，由于在没有给出插入条件的问题中，很难给出插入的具体方法。因此这里以在一棵二叉搜索树中插入为例。插入过程的核心思想，是按照给定的插入条件（例中为二叉查找树）找到树里面的边界（死胡同），此处就是查找失败的地方，也是结点需要插入的地方 void insert(node*& root, int x) { //注意 传入的是结点指针的引用 if (root == NULL) { //空树，即查找失败，插入结点（递归边界） root = newNode(x); return; } if (root->data > x) { //往左子树搜索 insert(root->lchild, x); } else insert(root->rchild, x); //往右子树搜索 } 在上述代码中，一个关键的点就是根节点指针root使用了引用&，这样在函数中可以直接修改原变量。这么做的原因是，在insert函数中新建了一个新结点，并且把新节点的地址赋给了当层的root。如果不采用引用，root = new node 这个语句对root 的修改就无法作用到原变量，也就无法将节点加到二叉树上面。那为什么前面的search 函数不需要加引用呢？因为search 函数修改的是指针root指向的内容，而不是root本身，对结点指向的内容的修改是不需要加引用的 4.二叉树创建过程 二叉树的创建，其实就是二叉树结点的插入过程，比较常用的写法是把需要插入的数据域存储在数组中，并且最终返回插入结点后树的根结点 node*create(int data[], int n) { node* root = NULL; //新建空根结点 for (int i = 0; i 左子树->右子树，由上文提到的抽象思想，对于每个结点都采用相同的遍历思路，直到到达递归边界所以核心问题是处理好 递归式与递归边界 实现效果图如下： 代码实现如下：
void preorder(node* root) { //先序遍历
if (root == NULL) return; //到达空树，即递归边界
cout 根节点->右子树，由上文提到的抽象思想，对于每个结点都采用相同的遍历思路，直到到达递归边界实现效果图如下：  代码实现如下：
void inorder(node* root) { //中序遍历
if (root == NULL) return; //到达空树，即递归边界
inorder(root->lchild); //访问左子树
cout 根节点，由上文提到的抽象思想，对于每个结点都采用相同的遍历思路，直到到达递归边界实现效果图如下：  代码实现如下：
void postorder(node* root) { //后序遍历
if (root == NULL) return; //到达空树，即递归边界
preorder(root->lchild); //访问左子树
preorder(root->rchild); //访问右子树
cout lchild = Node->rchild = NULL; //初始状态下无左右孩子
return Node; //返回新节点的地址
}
void search(node*root,int x, int newdata){
if (root == NULL) return; //考虑为空节点的可能性
if (root->data == x) {
root->data = newdata; //找到数据域为x的结点，把它修改为newdata
}
search(root->lchild, x, newdata);//往左子树搜索
search(root->rchild, x, newdata);//往右子树搜索
}
void insert(node*& root, int x) {
if (root == NULL) { //空树，即查找失败，插入结点（递归边界）
root = newNode(x);
return;
}
if (root->data > x) { //往左子树搜索
insert(root->lchild, x);
}
else insert(root->rchild, x); //往右子树搜索
}
node*create(int data[], int n) {
node* root = NULL; //新建空根结点
for (int i = 0; i |
【本文地址】
今日新闻 |
推荐新闻 |